/**
 * 快速排序
 *
 * @param {number[]} nums
 * @return {number[]}
 */
function quickSort(nums) {
  const length = nums.length;
  if (length < 2) {
    return nums;
  }
  sort(nums, 0, length - 1);
  return nums;
}

function sort(nums, left, right) {
  if (left < right) {
    const i = index(nums, left, right);
    sort(nums, left, i - 1);
    sort(nums, i + 1, right);
  }
}

function index(nums, left, right) {
  const pivot = nums[right];
  while (left < right) {
    while (left < right && nums[left] < pivot) {
      left++;
    }
    nums[right] = nums[left];
    while (left < right && nums[right] > pivot) {
      right--;
    }
    nums[left] = nums[right];
  }
  nums[right] = pivot;
  return left;
}

const nums = [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48];
console.log(quickSort(nums));
